package com.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序的核心思想:
 *      1.选择一个基准i,将小于i的数字都放在i左侧,大于i的放在右侧,则i一定在最终排序结果所在的位置
 *      2.组内排序:独特的数组内排序使其基本不多占任何空间 (哨兵前后扫描机制)
 *      3.分治 : 递归i左右两侧的数组排序,即可得到有序数组
 */
public class QuickSort {
    public static void main(String[] args) {
        Integer[] arr = {4, 1, 9, 3, 7, 5, 2, 6};
        //quickSort00(arr, 0, arr.length - 1);
        quickSort01(arr, 0, arr.length - 1);
    }


    /**
     *@author : daniel.yang
     *@date : 2018/11/14
     *@desc : 原始快排 => 在数组外排序后将其移入数组,浪费空间
     *@param arr :
     *@param start :
     *@param end :
     */
    public static void quickSort00(Integer[] arr, int start, int end) {
        if (start >= end){
            return ;
        }
        int index = partition00(arr, start, end);
        System.out.println(Arrays.toString(arr));
        quickSort00(arr,start,index -2);
        quickSort00(arr,index,end);
    }

    public static int partition00(Integer[] arr, int start, int end) {
        Integer pivot = arr[start];
        // 将数据复制出来排序
        Integer[] part = new Integer[end - start +1];
        int p = 0;
        int q = end - start;
        int index = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] <= pivot){
                part[p++] = arr[i];
                index ++;
            }else {
                part[q--] = arr[i];
            }
        }

        swap(part,0,p -1 );

        for (int i = start; i <= end; i++) {
            arr[i] = part[i-start];
        }
        return index;
    }

    /**
     *@author : daniel.yang
     *@date : 2018/11/14
     *@desc : 改进后的快排 => 直接在原数组内排序,不使用额外空间
     *@param arr :
     *@param start :
     *@param end :
     */
    public static void quickSort01(Integer[] arr, int start, int end) {
        if (start >= end){
            return;
        }
        int i = partition01(arr, start, end);
        //System.out.println(i+Arrays.toString(arr));
        quickSort01(arr,start,i-1);
        quickSort01(arr,i+1,end);
    }


    public static int partition01(Integer[] arr, int start, int end) {
        int i = partition01Pivot(arr, start, end, start);
        return i;
    }

    public static int partition01Pivot(Integer[] arr, int start, int end, Integer t) {
        int pivot = arr[t];
        int i = start;
        int j = end;
        while (i < j) {
            //System.out.println(Arrays.toString(arr));
           while (arr[i] < pivot){
               i++;
           }
           while (j>=0 && arr[j] >= pivot){
               j--;
           }
           if (i < j){
               swap(arr,i,j);
           }
        }
        return i;
    }

    public static void swap(Integer[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
